package com.xyhuo.leetcode.january;

import java.util.*;

/**
 * 克隆图
 * https://leetcode.cn/problems/clone-graph/
 *
 * @time 2024/1/17
 */
public class CloneGraph {

    public Node cloneGraph(Node node) {
        search(node);
        return ans;
    }

    private Map<Integer, Node> alreadyMap = new HashMap<>();

    private Node ans;

    private Node search(Node node) {
        if (null == node) {
            return null;
        }
        if (alreadyMap.containsKey(node.val)) {
            return alreadyMap.get(node.val);
        }
        Node cloneNode = new Node(node.val);
        alreadyMap.put(node.val, cloneNode);
        if (ans == null) {
            ans = cloneNode;
        }
        for (Node neighbor : node.neighbors) {
            Node cloneNeighbor = search(neighbor);
            cloneNode.neighbors.add(cloneNeighbor);
        }
        return cloneNode;
    }

    class Node {
        public int val;
        public List<Node> neighbors;

        public Node() {
            val = 0;
            neighbors = new ArrayList<Node>();
        }

        public Node(int _val) {
            val = _val;
            neighbors = new ArrayList<Node>();
        }

        public Node(int _val, ArrayList<Node> _neighbors) {
            val = _val;
            neighbors = _neighbors;
        }
    }
}
